package com.gzl.exercise;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringJoiner;

/**
 * @PROJECT_NAME: exercise
 * @NAME: 找到所有数组中消失的数字
 * @DESCRIPTION: 简单题
 * @USER: gaozengliang
 * @DATE: 2023/9/12
 */
public class 找到所有数组中消失的数字 {
    /**
     * 给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [4,3,2,7,8,2,3,1]
     * 输出：[5,6]
     * 示例 2：
     *
     * 输入：nums = [1,1]
     * 输出：[2]
     *
     *
     * 提示：
     *
     * n == nums.length
     * 1 <= n <= 10^5
     * 1 <= nums[i] <= n
     * 进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
     * */
    @Test
    void findDisappearedNumbers(){
        int[] nums = {1,1,2,2,2,2};
//        int[] nums = {1,1,2,2};
//        int[] nums = {4,3,2,7,7,2,3,1};
//        int[] nums = {4,3,2,8,8,2,3,1};
//        int[] nums = {1,1};
        int n = nums.length;
        List<Integer> list = new ArrayList<>();
        // 去重
        nums = Arrays.stream(nums).distinct().toArray();
        int n2 = nums.length;
//        System.out.println(n+" "+n2);
        // 排序
        Arrays.sort(nums);
        /*for (int num:nums){
            System.out.print(num+",");
        }
        System.out.println("\n");*/

        // 找出缺失的数值，如果数值与坐标不对应，说明该坐标的值缺失
        for (int i=0,j=1;i<n2;){
            //1,2,3,4,7,8
            if (nums[i] != j){
                list.add(j);
                j++;
            }else {
                i++;
                j++;
            }
        }
        // 如果list的大小没有缺失的多，缺几个说明最后几个缺失了
//        System.out.println(list.size());
        if (list.size()<n-n2){
            int l = list.size();
            for (int i=0, j=nums[n2-1]+1;i<n-n2-l;i++){
                list.add(j);
                j++;
            }
        }
        for (Integer num:list){
            System.out.println(num);
        }
//        return list;
    }

    @Test
    void reference(){
        int[] nums = {4,3,2,7,7,2,3,1};

        List<Integer> ans = new ArrayList<>();

        for (int i=0; i<nums.length; i++) {
            int val=Math.abs(nums[i])-1;
            if (nums[val]>0) {
                nums[val]=-nums[val];
            }
        }

        for (int i=0; i<nums.length; i++) {
            System.out.print(nums[i]+",");
            if (nums[i]>0) {
                ans.add(i+1);
            }
        }
        System.out.println();
        for (Integer num:ans){
            System.out.println(num);
        }
    }
}
